#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
//数据类型定义
typedef int ElemType;
//节点定义
typedef struct LinkedNode{
    ElemType data;//数据域
    struct LinkedNode *next;//指针域
}LinkedNode ,*LinkedList;


//例题21、建立带头结点的循环链表。★★
LinkedList createCircleLinkedList(ElemType *dataArr,int arrLen){
    //创建头节点
    LinkedList list = (LinkedList) malloc(sizeof (LinkedNode));
    if(!list) return NULL;
    list->next = NULL;//防止不小心访问到，产生野指针

    //插入节点
    LinkedNode * head = list;
    for(int i = 0; i < arrLen;i++){
        //新建节点
        LinkedNode * node = (LinkedNode *) malloc(sizeof (LinkedNode));
        node->data = dataArr[i];
        node->next = NULL;
        //插入链表（尾插）
        list->next = node;
        list = list->next;
    }
    //首尾相接
    list->next = head;
    return head;
}

//例题24、设计算法将循环单链表中节点p的直接前驱删除。★★★
void deletePreNode(LinkedNode *p){
    LinkedNode * pre = p;
    LinkedNode * cur = p->next;
    while(cur->next != p){
        cur = cur->next;
        pre = pre->next;
    }
    //此时cur指向p前驱（待删除的节点），pre指向前驱的前驱
    pre->next = p;
    free(cur);
}


//例题25、设计算法将一个含有数字、字母、其他字符组成的循环链表拆分成三个循环链表，每条链中只包含一种类型的字符。★★★
/*感觉。。没什么意思，一下是GPT的代码*/
LinkedList* splitToThree(LinkedList originalList){
    LinkedList numberList = NULL;   // 数字链表
    LinkedList letterList = NULL;   // 字母链表
    LinkedList otherList = NULL;    // 其他字符链表

    LinkedList currentNode = originalList;

    do {
        if (isdigit(currentNode->data)) {
            // 如果是数字，则插入到数字链表中
            if (numberList == NULL) {
                // 数字链表为空，则将当前节点作为头节点
                numberList = currentNode;
                currentNode->next = currentNode;  // 设置节点的 next 指针指向自身，构成循环链表
            } else {
                // 数字链表不为空，则将当前节点插入到链表末尾
                currentNode->next = numberList->next;
                numberList->next = currentNode;
                numberList = currentNode;
            }
        } else if (isalpha(currentNode->data)) {
            // 如果是字母，则插入到字母链表中
            if (letterList == NULL) {
                // 字母链表为空，则将当前节点作为头节点
                letterList = currentNode;
                currentNode->next = currentNode;  // 设置节点的 next 指针指向自身，构成循环链表
            } else {
                // 字母链表不为空，则将当前节点插入到链表末尾
                currentNode->next = letterList->next;
                letterList->next = currentNode;
                letterList = currentNode;
            }
        } else {
            // 其他字符，则插入到其他字符链表中
            if (otherList == NULL) {
                // 其他字符链表为空，则将当前节点作为头节点
                otherList = currentNode;
                currentNode->next = currentNode;  // 设置节点的 next 指针指向自身，构成循环链表
            } else {
                // 其他字符链表不为空，则将当前节点插入到链表末尾
                currentNode->next = otherList->next;
                otherList->next = currentNode;
                otherList = currentNode;
            }
        }

        currentNode = currentNode->next;
    } while (currentNode != originalList);

    LinkedList* result = malloc(3 * sizeof(LinkedList));
    result[0] = numberList;
    result[1] = letterList;
    result[2] = otherList;
    return result;
}

//例题27、已知La和Lb分别为两个循环单链表的头节点指针，m和分别为La和Lb中数据节点的个数，
//设计时间复杂度最小的算法将两个链表合并成一个带头的循环单链表。★★★
/*算法思想：依次访问较短的循环链表中的元素，并将其插入到另外一个链表中；重复上述步骤，直到短链中不存在待
插元素。*/
LinkedList combineCircleLinks(LinkedList la,LinkedList lb,int m,int n){

    //找到长短链表
    LinkedNode * longList = m>n?la:lb;
    LinkedNode * shortList = m>n?lb:la;

    LinkedNode * currNode = shortList->next;
    while (currNode != shortList){//注意：循环队列采用的遍历条件
        //把当前节点插入长的链表（头插方便）
        LinkedNode * tmp = currNode;//一定要有
        currNode = currNode->next;
        tmp->next = longList->next;
        longList->next = tmp;
    }
    free(shortList);
    return longList;
}


//例题28、创建尾指针指向的循环单链表。★★
LinkedList createCircleLinkedListWithRear(int *dataArr,int arrLen){
    //list最后将作为尾指针返回
    LinkedList list = (LinkedList *) malloc(sizeof (LinkedNode));
    LinkedList head = list;//头结点就是头结点，与头指、尾指针、头插尾插均无关系
    list->next = NULL;
    //使用尾插法构建
    for (int i = 0; i < arrLen; ++i) {
        LinkedNode * node = (LinkedNode *) malloc(sizeof(LinkedNode));
        node->data = dataArr[i];
        node->next = list->next;
        //尾插法
        list->next = node;
        list = list->next;
    }
    //插入完之后形成循环
    list->next = head;

    return list;
}

//例题29、请设计一种数据结构来存储带头结点的循环单链表La和Lb,使得两链合并时的效率尽可能高。★★★
/*算法思想：Lα链和Lb链使用带尾结点指针的循环单链表。将Lα链的尾结，点指针指向Lb链的第一个数据结点，然后
            将Lb链的尾结点指针指向L链的结点。*/
LinkedNode * combineCircleLinksFast(LinkedList la,LinkedList lb){
    //将a做为主串，保留其头结点
    LinkedNode * aHead = la->next;
    LinkedNode * bHead = lb->next;
    la->next = bHead->next;
    lb->next = aHead;
    free(bHead);
    la = lb;

    //依旧放回尾指针
    return la;
}



//打印
void shift(){
    printf("\n");
}
//遍历循环列表
void traverseLinkedList(LinkedList list){
    //传进来的是头结点
    LinkedNode * curr = list->next;
    while(curr && curr != list){
        printf("%d ",curr->data);
        curr = curr->next;
    }
}
//测试
int main(){

    int arr1[5] = {5,5,5,5};
    int arr2[5] = {1,1,1,1,1};
    int arr3[5] = {1,2,3,4,5};
    LinkedList list1 = createCircleLinkedList(arr1,4);
    LinkedList list2 = createCircleLinkedList(arr2,5);
    LinkedList list3 = createCircleLinkedListWithRear(arr3,5);

//    traverseLinkedList(list1);shift();
//    deletePreNode(list1->next->next->next);
//    traverseLinkedList(list1);shift();

//    LinkedList list3 = combineCircleLinks(list1,list2,4,5);
//    traverseLinkedList(list3);
//
//    traverseLinkedList(list3->next);

    return 0;
}